package SwordOffer2;

import java.util.HashMap;

public class day4_1 {
    /*
     * 下标前置和：
     * 1.创建HashMap用于标记（sum，子数组个数），sum记录下标之前的和
     * 2.循环数组：sum累计nums[0]到nums[i]的和，
     *           判断hashmap中是否包含sum-k的值，若有表示存在一个子数组累计和为k，count加上hashmap中sum-k的value值
     *           hashmap记录下sum，和sum的value值加1
     *           （若sum1到sum2且sum1等于sum2的值为k，则必存在一个数组和为k，hashmap的初始key赋值0，value赋值1）
     * 3.返回值count
     * */
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            // System.out.println("sum "+sum);
            count += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            //System.out.println("sum1 "+sum);
        }
/*        for (Integer i:map.keySet()){
            System.out.println("key "+i+"value "+map.get(i));
        }*/
        return count;
    }
}
